UVa/442 - Matrix chain multiplication/442.cpp

   1 #include <iostream>
   2 #include <map>
   3 #include <cassert>
   4
   5 using namespace std;
   6
   7 typedef pair<int, int> par;
   8
   9 string line;
  10 int total, pos;
  11 bool error;
  12 map<char, par> d;
  13
  14 void match(const string &s){
  15   //cout << "Matching: " << s << endl;
  16   for (int i=0, n = s.size(); i<n; ++i){
  17     assert(line[pos++] == s[i]);
  18   }
  19 }
  20
  21 par E(){
  22   if (line[pos] == '('){
  23     match("(");
  24     par a = E();
  25     par b = E();
  26     //cout << "a es: (" << a.first << ", " << a.second << ")" << endl;
  27     //cout << "b es: (" << b.first << ", " << b.second << ")" << endl;
  28     if (a.second != b.first){
  29       error = true;
  30     }
  31     match(")");
  32     total += a.first * a.second * b.second;
  33     return par(a.first, b.second);
  34   }else if ('A' <= line[pos] && line[pos] <= 'Z'){
  35     char c = line[pos];
  36     match(string(1, c));
  37     return d[c];
  38   }
  39 }
  40
  41 int main(){
  42   int n;
  43
  44   cin >> n;
  45   while (n--){
  46     char c;
  47     int x, y;
  48     cin >> c >> x >> y;
  49     d[c] = par(x, y);
  50   }
  51   getline(cin, line);
  52   while (getline(cin, line) && line != ""){
  53     //cout << "line es: " << line << endl;
  54     total = pos = 0;
  55     error = false;
  56     E();
  57     if (error)
  58       cout << "error" << endl;
  59     else
  60       cout << total << endl;
  61   }
  62   return 0;
  63 }